#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/
#define kMinSize 5 /* 最小规模必须大于alpha */
#define alpha 4
#define infinity (1e9)
typedef struct SubProblemNode *SubProblems;
struct SubProblemNode {
    int l; /* 子问题的左端点 */
    int n; /* 子问题的规模   */
};

ElemSet Min(ElemSet x, ElemSet y) {
    return (x < y) ? x : y;
}

ElemSet Max(ElemSet x, ElemSet y) {
    return (x < y) ? y : x;
}

void Conquer(ElemSet *a, int l, int n) {
    /* 插入排序 */
    ElemSet t;
    int i, j, r;

    r = l + n - 1;
    for (i = l + 1; i <= r; i++) {
        t = a[i];
        for (j = i; j >= (l + 1); j--) {
            if (a[j - 1] > t) {
                a[j] = a[j - 1];
            } else {
                break;
            }
        }
        a[j] = t;
    }
}

SubProblems Divide(int l, int n, int m) {
    /* 将规模为n的问题均分为m个子问题 */
    int size, i;
    SubProblems p;

    p = (SubProblems)malloc(sizeof(struct SubProblemNode) * m);
    size = n / m; /* 每个子问题的规模 */
    for (i = 0; i < m; i++) {
        p[i].l = l + i * size; /* 子问题的左端点 */
        p[i].n = size;
    }
    p[m - 1].n = l + n - p[m -
                           1].l; /* n可能不能被m整除，最后一个问题的规模特殊处理 */
    return p;
}

ElemSet *Merge(ElemSet *a, SubProblems part, int n) {
    ElemSet *t;
    int p[alpha], pt, min_elem, min_idx, i;

    t = (ElemSet *)malloc(sizeof(ElemSet) * n);
    for (i = 0; i < alpha; i++) {
        p[i] = part[i].l; /* 每个子问题的当前元素位置 */
    }
    for (pt = 0; pt < n; pt++) {
        min_elem = infinity;
        for (i = 0; i < alpha; i++) { /* 找所有子问题当前元素的最小值 */
            if (p[i] < (part[i].l + part[i].n) && a[p[i]] < min_elem) {
                min_elem = a[p[i]];
                min_idx = i;
            }
        }
        t[pt] = a[p[min_idx]]; /* 放入t中 */
        p[min_idx]++;
    }
    return t;
}

/* 算法15-7 分治法的伪代码描述 DivideAndConquer(n) */
void DivideAndConquer(ElemSet *a, int l, int n) {
    int i;
    ElemSet *solution;
    SubProblems part;

    if (n < kMinSize) { /* 若问题规模小于给定阈值 */
        Conquer(a, l, n); /* 直接处理 */
    } else {
        part = Divide(l, n,
                      alpha); /* 将规模为 n 的原问题分割为alpha个子问题 */
        for (i = 0; i < alpha; i++) {
            DivideAndConquer(a, part[i].l, part[i].n);
        }
        solution = Merge(a, part,
                         n); /* 将alpha个子问题的解合并得到最终解 */
        for (i = 0; i < n; i++) { /* 归并排序需要将solution复制回a */
            a[l + i] = solution[i];
        }
    }
}
/* 算法15-7 结束 */

int main(void) {
    ElemSet *a;
    int n, i;

    scanf("%d", &n);
    a = (ElemSet *)malloc(sizeof(ElemSet) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    DivideAndConquer(a, 0, n);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}